#include <iostream>
#include <string.h>

using namespace std;

static const int types = 4;

void DNASort(char** data, int lines)
{
	int* disorder = new int[lines];

	int count[types];
	int s[types];

	for(int i=0;i<lines;i++)
	{
		disorder[i] = 0;
		for(int j=0;j<types;j++)
			count[j]=0;

		//count
		for(int j=0;j<strlen(data[i]);j++)
			switch(data[i][j])
			{
				case 'A':
					count[0]++;
					break;
				case 'C':
					count[1]++;
					break;
				case 'G':
					count[2]++;
					break;
				case 'T':
					count[3]++;
					break;
				default:
					cout<<"character error"<<endl;
			}

		//cout<<"count: "<<count[0]<<count[1]<<count[2]<<count[3]<<endl;
		
		//accumulative
		s[0]=0;
		for(int k=1;k<types;k++)
		{
			count[k] += count[k-1];
			s[k]=count[k-1];
		}
		//cout<<"s: "<<s[0]<<s[1]<<s[2]<<s[3]<<endl;

		for(int j=0;j<strlen(data[i]);j++)
		{
			//cout<<"j: "<<j<<" "<<data[i][j]<<endl;
		  //cout<<"s: "<<s[0]<<s[1]<<s[2]<<s[3]<<endl;
			switch(data[i][j])
			{
				case 'A':
					s[1]--;
					s[2]--;
					s[3]--;
					break;
				case 'C':
					disorder[i] += s[1];
					s[2]--;
					s[3]--;
					break;
				case 'G':
					disorder[i] += s[2];
					s[3]--;
					break;
				case 'T':
					disorder[i] += s[3];
					break;
				default:
					cout<<"character error"<<endl;
			}
		  //cout<<"s: "<<s[0]<<s[1]<<s[2]<<s[3]<<endl;
			//cout<<"disorder[i]: "<<disorder[i]<<endl;
		}

		//cout<<disorder[i]<<endl;
	}

	for(int i=1;i<lines;i++)
	{
		for(int j = i;j>0;j--)
		{
			if(disorder[j] < disorder[j-1])
			{
				int temp = disorder[j];
				disorder[j] = disorder[j-1];
				disorder[j-1] = temp;

				char* ptemp = data[j];
				data[j]=data[j-1];
				data[j-1] = ptemp;
			}
			else
				break;
		}
	}

	for(int i=0;i<lines;i++)
		cout<<data[i]<<endl;

	delete []disorder;
}

int main()
{
	int lines, length;
	cin>>length>>lines;
	char** data = new char*[lines];
	//cout<<"lines: "<<lines<<" length: "<<length<<endl;
	for(int i=0;i<lines;i++)
	{
		data[i] = new char[length+1];
		cin>>data[i];
		//cout<<data[i]<<endl;
	}

	DNASort(data, lines);

	for(int i =0;i<lines;i++)
		delete []data[i];
	delete []data;

	return 0;
}
